package sort.merge;

/**
 * @author justnow
 * Created on 2020-08-31
 * Description
 *
 * https://www.cnblogs.com/chengxuyuanzhilu/p/6133568.html
 * https://www.cnblogs.com/of-fanruice/p/7678801.html
 *
 */
public class MergeSort {
    public static int[] sort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边的拆分
            sort(a, low, mid);
            // 右边的拆分
            sort(a, mid + 1, high);
            // 左右的归并
            merge(a, low, mid, high);
        }
        return a;
    }

    private static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左边数组的起始指针
        int j = mid + 1; // 右边数组的起始指针
        int k = 0;// 合并数组的起始指针

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }

        //把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = a[i++];
        }

        //把右边剩余的数移入数组
        while (j <= high) {
            temp[k++] = a[j++];
        }

        //把新数组中覆盖给原始数组
        for (int l = 0; l < temp.length; l++) {
            a[low + l] = temp[l];
        }
    }

    public static void main(String[] args) {
        int[] nums = {12, 4, 13, 25, 92, 11, 9, 3, 2};
        MergeSort.sort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
